class Solution {
public:
    ListNode* sortList(ListNode* head) {
      if(head==nullptr||head->next==nullptr) return head;
       ListNode* dHead = new ListNode(0);
       dHead->next=head;
       ListNode* p=dHead,*last=head,*r=head->next;
       while(r!=nullptr){
         if(last->val<=r->val){
           last=last->next;
         }else{
           p=dHead;
           while(p->next->val<r->val){
             p=p->next;
           }
           last->next=r->next;
           r->next=p->next;
           p->next=r;
         }
         r=last->next;
       }
       return dHead->next;
    }
};
